import java.util.Arrays;

public class Solution654 {

    private int getMaxNumInd(int[] nums, int begin, int end){
        int maxNum = Integer.MIN_VALUE, maxInd = 0;
        for (int i = begin; i <= end; i++) {
            int tmpNum = nums[i];
            if(tmpNum > maxNum){
                maxNum = tmpNum;
                maxInd = i;
            }
        }
        return maxInd;
    }

    private TreeNode doBuild(int[] nums, int begin, int end){
        if(begin > end){
            return null;
        }
        int maxInd = getMaxNumInd(nums, begin, end);
        TreeNode node = new TreeNode(nums[maxInd]);
        node.left = doBuild(nums, begin, maxInd - 1);
        node.right = doBuild(nums, maxInd + 1, end);
        return node;
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return doBuild(nums, 0, nums.length - 1);
    }
}
